package code.oldCode.feishuSpecializedTraining.dynamic;

public class MyDP12 {
    public int countSubstrings(String s) {
        // 1 <= s.length <= 1000
        int len = s.length();
        // dp[i][j]表示第i到j个字符组成的字符串的回文串个数
        int[][] dp = new int[len][len];
        // isOK[i][j]表示第i到j个字符组成的字符串是否为回文串
        boolean[][] isOK = new boolean[len][len];
        // 初始化:gap=0先找单个字符，它一定是回文子串;gap=1再找两个字符的，相等则是回文子串
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
            isOK[i][i] = true;
        }
        for (int i = 0; i < len - 1; i++) {
            // gap=1时，相等则三个，不相等则两个
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 3 : 2;
            isOK[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        // 斜着遍历，找三个字符以上的，找首尾俩字符 gap>=2
        for (int gap = 2; gap < len; gap++) {
            for (int start = 0; start < len - gap; start++) {
                int end = start + gap;
                // gap>=2时，找start~end的回文串个数，找start~end-1，start+1~end，再把重复的start+1~end-1去掉
                // 如果start~end是回文串，则加一
                isOK[start][end] = s.charAt(start) == s.charAt(end) && isOK[start + 1][end - 1];
                dp[start][end] = dp[start][end - 1] + dp[start + 1][end] - dp[start + 1][end - 1];
                dp[start][end] += isOK[start][end] ? 1 : 0;
            }
        }
        return dp[0][len - 1];
    }

    // 516. 最长回文子序列
    public int longestPalindromeSubseq(String s) {
        // 1 <= s.length <= 1000
        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < len - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 2 : 1;
        }
        // 斜着遍历
        for (int gap = 2; gap < len; gap++) {
            for (int start = 0; start < len - gap; start++) {
                int end = start + gap;
                if (s.charAt(start) == s.charAt(end))
                    dp[start][end] = dp[start + 1][end - 1] + 2;
                else
                    dp[start][end] = Math.max(dp[start + 1][end], dp[start][end - 1]);
            }
        }
        return dp[0][len - 1];
    }

    public static void main(String[] args) {
        MyDP12 m = new MyDP12();
        System.out.println(m.countSubstrings("abc"));
    }
}
